/*
 * @lc app=leetcode.cn id=54 lang=cpp
 *
 * [54] 螺旋矩阵
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        const int row_num = matrix.size();
        const int col_num = matrix[0].size();
        vector<vector<bool>> visited(row_num, vector<bool>(col_num, 0));
        // cout << visited.size() << " " << visited[0].size() << endl;
        vector<int> ans;
        int last_size = 0;

        int row = 0, col = 0;
        do
        {
            last_size = ans.size();

            if(col < 0 || row < 0 || col >= col_num || row >= row_num) break;
            for (; col < col_num && !visited[row][col]; col++)
            {
                visited[row][col] = true;
                ans.push_back(matrix[row][col]);
            }
            col--;
            // cout << row << "," << col << "\t";
            if(col < 0 || row < 0 || col >= col_num || row >= row_num) break;

            for (row++; row < row_num && !visited[row][col]; row++)
            {
                visited[row][col] = true;
                ans.push_back(matrix[row][col]);
            }
            row--;
            // cout << row << "," << col << "\t";
            if(col < 0 || row < 0 || col >= col_num || row >= row_num) break;


            for (col--; col >= 0 && !visited[row][col]; col--)
            {
                visited[row][col] = true;

                ans.push_back(matrix[row][col]);
            }
            col++;
            // cout << row << "," << col << "\t";
            if(col < 0 || row < 0 || col >= col_num || row >= row_num) break;


            for (row--; row >= 0 && !visited[row][col]; row--)
            {
                visited[row][col] = true;

                ans.push_back(matrix[row][col]);
            }
            row++, col++;
            // cout << row << "," << col << "\t";
            if(col < 0 || row < 0 || col >= col_num || row >= row_num) break;

            // cout << endl;
        } while (ans.size() > last_size);

        return ans;
    }
};
// @lc code=end
